package medium;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/*
139. 单词拆分
解题思路：动态规划
 */
public class LeeCode139 {

  public static void main(String[] args) {
    ArrayList<String> wordDict = new ArrayList<>();
    wordDict.add("cats");
    wordDict.add("dog");
    wordDict.add("sand");
    wordDict.add("and");
    wordDict.add("cat");
    System.out.println(new LeeCode139().wordBreak("catsandog", wordDict));
  }

  public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> wordDictSet = new HashSet(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
      for (int j = 0; j < i; j++) {
        String s1 = s.substring(j, i);
        if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp[s.length()];
//    HashSet<String> wordDictSet = new HashSet<>(wordDict);
//    boolean[] dp = new boolean[s.length() + 1];
//    for (int i = 1; i <= s.length() ; i++) {
//      for (int j = 0; j < i; j++) {
//        if (wordDictSet.contains(s.substring(j,i))){
//          dp[i] = true;
//          break;
//        }
//      }
//    }
//    return dp[s.length()];
  }
}
